package com.example.demo.algorithms;

import cn.hutool.core.collection.CollectionUtil;
import lombok.Data;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.stream.Collectors;

/**
 * <p>Description: 广度遍历</p>
 *
 * @author Eric Lee
 * @version v1.0.0
 * @since 2021/12/18 21:59
 **/
public class BFS {
    @Data
    public class Department {
        private Long id;
        private String name;
        private List<Department> children;

        public Department(Long id, String name) {
            this.id = id;
            this.name = name;
        }
    }

    @org.junit.Test
    public void test2() {
        Department xuexiao = init();
        List<Department> data = findByBFS("语文", xuexiao);
        List<Long> result = data.stream().map(s -> s.id).collect(Collectors.toList());
    }

    /**
     * 初始化邻接链表数据
     *
     * @return
     */
    public Department init() {
        Department xuexiao = new Department(1L, "学校");
        List<Department> xuexiaochildren = new ArrayList<>();
        Department nianji1 = new Department(2L, "一年级");
        List<Department> nianji1Child = new ArrayList<>();
        nianji1Child.add(new Department(5L, "语文"));

        Department shuxue = new Department(6L, "数学");
        List<Department> shuxueChild = new ArrayList<>();
        shuxueChild.add(new Department(9L, "数学一组"));
        shuxue.setChildren(shuxueChild);
        nianji1Child.add(shuxue);

        nianji1.setChildren(nianji1Child);

        Department nianji2 = new Department(3L, "二年级");
        List<Department> nianji2Child = new ArrayList<>();
        nianji2Child.add(new Department(7L, "语文"));
        nianji2.setChildren(nianji2Child);

        Department nianji3 = new Department(4L, "三年级");
        List<Department> nianji3Child = new ArrayList<>();
        nianji3Child.add(new Department(8L, "英语"));
        nianji3.setChildren(nianji3Child);

        xuexiaochildren.add(nianji1);
        xuexiaochildren.add(nianji2);
        xuexiaochildren.add(nianji3);
        xuexiao.setChildren(xuexiaochildren);
        return xuexiao;
    }

    /**
     * 广度优先遍历，查找指定元素
     *
     * @param word
     * @param department
     * @return
     */
    public List<Department> findByBFS(String word, Department department) {
        List<Department> result = new ArrayList();
        Queue<Department> queue = new LinkedList<>();
        queue.add(department);
        while (!CollectionUtil.isEmpty(queue)) {
            Department temp = queue.poll();
            if (word.equals(temp.name)) {
                result.add(temp);
            }
            List<Department> children = temp.getChildren();
            if (null != children) {
                for (Department child : children) {
                    queue.add(child);
                }
            }

        }
        return result;
    }
}
